1. Technical Field of the Invention
This invention relates generally to data communications and more particularly to encoding and decoding of data within such communication systems.
2. Description of Related Art
As is known, communication systems include a plurality of communication devices (e.g., modems, personal computers, laptops, cell phones, radios, telephones, facsimile machines, et cetera) that communicate directly (i.e., point to point) or indirectly via communication system infrastructure (e.g., wire line channels, wireless channels, bridges, switches, routers, gateways, servers, et cetera). As is also known, a communication system may include one or more local area networks and/or one or more wide area networks to support at least one of the Internet, cable services (e.g., modem functionality and television), wireless communication systems (e.g., radio, cellular telephone), satellite services, wire line telephone services, et cetera.
In any type of communication system, information (e.g., voice, audio, video, text, data, et cetera) is transmitted from one communication device to another via the infrastructure. Accordingly, the transmitting communication device prepares the information for transmission to the other device and provides the prepared information to the infrastructure for direct or indirect routing to the receiving communication device. For indirect routing, a piece of infrastructure equipment (e.g., server, router, et cetera) receives the prepared information and forwards it to another piece of infrastructure equipment or to the receiving communication device. The prepared information is thus propagated through the infrastructure until it reaches the receiving communication device. Once received, the receiving communication devices traverses the processing steps used by the transmitting communication device to prepare the information for transmission to recapture the original information.
As is further known, transmission of information between communication devices is not performed in an ideal environment where the received information exactly matches the transmitted information. In practice, the infrastructure introduces error, which distorts the transmitted information such that the received information does not exactly match the transmitted information. To compensate for the error introduced by the infrastructure, the transmitting communication device includes an encoder, which adds redundancy to the original data to make the original data more unique, and the receiving communication device includes a corresponding decoder, which uses the redunancy information to recover the original data from the received data that includes transmission errors.
As is known, there are two general types of coding in common use: block coding and convolution coding. In general, a block coding encoder divides information sequences into message blocks and converts each message block into a code word independently. A convolutional encoder encodes message blocks into a corresponding code word but does so based on previous, in time, message blocks.
As is also known, there are a variety of block coding schemes including linear block encoding, Reed-Solomon encoding, cyclic encoding, and BCH (Bose-Chadhuri-Hocquenghem) encoding, etc. FIG. 1 is a schematic block diagram of a transmitting communication device providing prepared information to a receiving communication device that utilizes BCH encoding. The transmitting communication device includes a data source, channel encoder, and a modulator. The receiving communication device includes a demodulator, channel decoder, and a data destination. The channel represents the communication system infrastructure.
The data source of the transmitting communication unit generates the original information as a series of k-bit data messages (u) that may be represented as polynomials [e.g., u(x)=u0x0+u1x1+u2x2+ . . . +Ukxk]. Depending on the type of transmitting communication device, the data source may generate digitized voice messages, digitized audio messages, digitized video messages, text messages, data messages and/or a combination thereof. The channel encoder receives the k-bit data messages and converts them into n-bit code words (v) [e.g., u(x)=v0x0+v1x1+v2x2+ . . . +vnxn] based on a polynomial generator [G(x)]. Such BCH encoding will be described in greater detail with reference to FIGS. 5 and 6.
As is known, BCH block codes have unique mathematical properties. For instance, a modulo 2 addition of any two binary codewords yields another valid codeword. Further, only a small subset of available digital values, or vectors in an n dimensional vector space over GF(2), are included in the set of valid codewords, or code block, and have a certain number of bit positions (i.e., polynomial coefficients) that differ from each other codeword. The amount of difference between each valid code word with respect to the overall size of the codeword is generally referred to as a minimum distance (dmin). The minimum distance indicates how many bits of the received code word can be in error and still accurately decoded to recapture the original information. In general, the number of correctable bits (t) equals the minimum distance minus 1 divided by two [i.e., t=½(dmin−1)].
For systematic encoding, the resulting n-bit codeword (v) includes the k-bit data message (u) and also includes n−k parity message. For BCH encoding, the k-bits of the data message and the n−k parity bits correspond to coefficients of the resulting polynomial codeword [v(x)]. The values of n and k vary depending on the size of the BCH block code. For example, a simple form of BCH block coding has an n of 7 (i.e., the codewords are seventh order polynomials) and a k of 4 (i.e., the data messages are fourth order polynomials). Of course, the values of n and k may increase to relatively large numbers. For example, n may be 214 (e.g., 16,384) and k may be 15,368.
As mentioned above, encoding is based on mathematical properties that result is a set of codewords that is a small subset of all possible digital values. For example, as illustrated in FIG. 2, a 7-bit word has 128 different values, yet a (7, 4) [i.e., n=7 and k=4] code block includes only 16 digital values as valid codewords, which are shown in bold in FIG. 2 and summarized in FIG. 3. The first three bits, which are in bit positions 0-2, are the n−k parity bits and the remaining four bits, which are in bit positions 3-6, are the k data message bits. As can be seen, each codeword differs from each other codeword in at least three bit positions. For example, codeword 001 0111 differs from codeword 001 1010 in the third, fourth, and sixth bit positions. Thus, this code block has a minimum distance of three. Accordingly, this code block has one-bit error correcting capabilities (i.e., t=½(3−1)=1).
FIG. 4 illustrates an example of correctable error vectors (i.e., received words that are not valid codewords but differ from a valid codeword by 1 bit). For example, received digital words 000 0001, 000 0010, 000 0100, 000 1000, 001 0000, 010 0000, and 100 0000 may be corrected to valid codeword 000 0000, since they differ by only one bit from the valid code word 000 0000. As such, as long as the received digital word differs from a valid codeword in t (number of correctable bits) or fewer bit locations, the received word may be accurately decoded to recapture the original data message.
Returning to the discussion of FIG. 1, the modulator modulates the n-bit codeword (v) utilizing a modulation scheme in accordance with one or more standards to which the transmitting communication device is compliant. For example, the modulation may be done in accordance with one or more cable modem standards, wireless communication standards, etc. The modulated code word is then transmitted via a wireline or wireless communication channel to the receiving communication device.
Within the receiving communication unit, the demodulator receives a digital word (r), which corresponds to the transmitted codeword (v) plus any error (e) that was introduced by the channel (or storage element). The demodulator demodulates the received word (r) in accordance with the standard or standards in which the codeword (v) was modulated to produce a demodulated received polynomial r(x).
The channel decoder receives the demodulated received polynomial r(x) and determines whether the received polynomial corresponds to a valid code word, which is typically done by calculating syndrome. Syndrome, which will be described in greater detail with reference to FIGS. 7 and 8, generally corresponds to a remainder value when the received polynomial r(x) is divided by the polynomial generator [g(x)]. When the syndrome is zero, i.e., the remainder was zero, then the received polynomial corresponds to a valid code word. If at least one syndrome values is not zero, i.e., the remainder was not zero, then the received polynomial does not correspond to a valid codeword.
If the received polynomial corresponds to a valid codeword, the codeword is processed to recapture the original data message (u). In practice, for systematically encoded data messages, the original data message is obtained by simply extracting the first k-bits of the valid codeword. The data destination receives the recovered data message and processes it accordingly.
If the received polynomial [r(x)] does not correspond to a valid code word, the channel decoder determines the error introduced by the channel based on the syndrome values. In essence, the determination of the error is determining which one of a plurality of error patterns that produce the same syndrome as the received polynomial [r(x)], is the most likely error pattern, or error polynomial, that distorted the transmitted codeword [v(x)]. Typically, the error pattern of the plurality of error patterns will be the one having the least number of ones. The determination of the error pattern will be described in greater detail with reference to FIGS. 7 and 9.
Having determined the error pattern the channel decoder determines the bit location, or locations, of the received polynomial [r(x)] that are in error based on the error pattern. Once the bit location, or locations, of error are identified, the decoder corrects the received polynomial accordingly to recapture a valid codeword. The recovered data message (u) is extracted from the valid codeword (v) as previously described.
FIG. 5 is a graphical representation of a prior art BCH (Bose-Chaudhuri-Hocquenghem) block encoder. In general, BCH block encoding utilizes a generator polynomial [g(x)] to produce a codeword [v(x)] in a polynomial form. As shown, the data message (u) is treated as a polynomial [u(x)], where the coefficients of the polynomial are the bits of the data message, where u0 is a coefficient for x0, u1 is a coefficient for x1, u2 is a coefficient for x2, . . . , and uk−1 is a coefficient for xk−1. The coefficient of the highest degree of x is transmitted first.
For systematic encoding (i.e., the k-bit data message is included, unaltered and in order, in the resulting codeword with the parity bits), the data message polynomial [u(x)] is multiplied by xn−k to raise the power to correspond to the power of the n-bit codeword polynomial [v(x)]. The resulting product of [u(x)] times xn−k is modulo divided by the generator polynomial [g(x)]. The generator polynomial is the least common multiple of one or more minimal polynomials of α, α2, α3, . . . , α2t, where α is a primitive element of the GF(m), with m=2n−1.
The remainder of the modulo division of [u(x)] times xn−k by the generator polynomial [g(x)] is summed with the product of [u(x)] times xn−k to produce the code word polynomial v(x), where v(x)=v0+v1x+v2x2+ . . . +vn−1xn−1. Accordingly, vn−1 corresponds to uk−1, vn−2 corresponds to uk−2, . . . vn−k+1 corresponds to u1, and vn−k corresponds to u0. Further, vn−k−1 corresponds to parity bit pn−k−1, . . . , v1 corresponds to p1, and v0 corresponds to p0.
FIG. 6 illustrates two prior art examples of a (7, 4) BCH block encoding, where n=7 and k=4. In the first example, a data message of 1011 is converted into a corresponding data message polynomial u(x)=1+x2+x3. For a (7, 4) single bit correction code block, the polynomial generator g(x)=1+x+x3. The data message polynomial is multiplied by Xn−k, where n−k equals 3 in this example producing a result of x3+x5+x6. This resultant is then divided by 1+x+x3, yielding a remainder of 1. Adding the remainder to the product of u(x)*xn−k produces the codeword polynomial v(x)=1+x3+x5+x6, which in a linear block binary form corresponds to a codeword of 1001011.
The second example has a data message of 0011, which is converted into a data message polynomial u(x)=x2+x3. Multiply the data message polynomial by xn−k, where n−k equals 3 in this example, yields x5+x6. Dividing the resulting product by the generator polynomial g(x), which is the same as in the first example, i.e., 1+x+x3, produces a remainder of x. Adding the remainder to the product of u(x)*xn−k produces the codeword polynomial v(x)=x+x5+x6, which in a linear block binary form corresponds to a codeword of 0100001.
FIG. 7 is a schematic block diagram of a prior art BCH decoder that includes a buffer, syndrome calculation module, error locator polynomial module, Chien search module and a subtraction module. The received polynomial r(x) is stored in the buffer and provided to the syndrome calculation module. In general, the syndrome calculation module performs a modulo division of the received polynomial r(x) by the polynomial generator g(x) to produce a plurality of syndrome values s(x). In mathematical terms, the syndrome values are defined as Si=R(αi), where R(x) is the remainder polynomial of r(x) mod g(x). If the remainder is 0, then the syndrome is 0, which indicates that the received polynomial r(x) is a valid codeword polynomial. If the remainder is not 0, then the syndrome is not 0, which indicates that the received polynomial r(x) includes error. A more detailed discussion of the syndrome calculation module will be provided with reference to FIG. 8.
The error locator polynomial module, which may perform a Berlekamp-Massey algorithm or Euclid's algorithm, receives the syndrome values and determines an error locator polynomial A(x).
The Chien search module, which will be described in greater detail with reference to FIG. 10, receives the error locator polynomial Λ(x) and determines the location of the error in the received polynomial therefrom. In general, the Chien search module tests potential error locations in succession starting with at a given time and exhausts all possible error locations to determine the actual error locations. After completion of the testing, the error locations are provided to the subtraction module, which removes the error from the received word, yielding a valid codeword polynomial.
FIG. 8 is a schematic block diagram of a prior art syndrome calculation module that produces one of 2t (2 times the number of correctable bits) syndrome values for the prior art BCH decoder. As such, the syndrome calculation module includes a plurality of the circuits shown in FIG. 8 to calculate the syndrome values. As shown, a syndrome value calculation circuit includes an adder, a multiplier and a register. The multiplier is operably coupled to multiple the output of the register (i.e., an intermediate syndrome value) with a primitive element αj+m0 (shown as aj+m0) of a GF(2m). The resulting product is added with the input (i.e., a coefficient of the received polynomial) to produce an intermediate syndrome value, which is stored in the register. As such, for each clock cycle, the degree of the input polynomial r(x) is reduced by one.
For high data rate applications (e.g., in the multiple gigabit-per-second (GBPS) range) that may include a large n, k, and t (i.e., number of bits in the code word, number of bits in the data message, and number of correctable bits), the syndrome calculation module of FIG. 8 has several issues that limit its applicability to lower data rate applications. For instance, the syndrome calculation module may be required to process m symbols per clock cycle, which for high data rate applications requires excessively fast circuitry. For example, if the data rate is 10.7 GBPS and the decoder clock rate is 167.3 MHz, the decoder must process 64 input bits in one clock cycle, which exceeds the processing capabilities of commercially available and economical processors. In addition, the number of multipliers is significant (e.g., 2t=146 for a minimum distance of 147), thus requiring a significant amount of integrated circuit die area. As such, the syndrome calculation module of FIG. 8 would be quite cumbersome and would be too slow for high data rate applications (e.g., data rates in excess of 1 GBPS), which may have large n, k, and t values (e.g., n=214, k=15,368, and t=74).
FIG. 9 is a schematic block diagram of a Chien search module that includes a plurality of multipliers, registers and a summation module, where α1 through αt are power of the primitive element. In general, the Chien search module receives the coefficients of the error locator polynomial Λ(x) from the error locator polynomial module. The Chien search module uses the Chien search algorithm to test if each time index is a root of the error locator polynomial. If the error locator polynomial is zero for time index i, the error vale is added with the value of the symbol at time index i of the code word. In this configuration, summing the register outputs at index (i) tests whether Λ(α−i)=0. If so, α−1 is a root of the error locator polynomial and indicates an error exists at the indexed location. To test at index i−1 requires multiplying the kth register contents by αk for all k in Λki−1=Λki αk and summing the contents again.
This procedure is repeated for each time index until the all of the time indexes have been tested. As such, regardless of whether the received polynomial includes one error or up to t errors, the Chien search module does a complete analysis of the error locator polynomial as just described. Accordingly, the same amount of processing time and power consumption is expended regardless of whether the received polynomial has one error or the maximum allowable.
FIG. 10 is a graphical representation of a prior art pipelined BCH decoding process. As shown, over time, the syndrome module, error locator polynomial module and Chien search module each perform their respective functions. For example, at time T-2, the syndrome module calculates the syndrome for received word number 1. At time T-1, the syndrome module calculates the syndrome for received word number 2, while the error locator polynomial module calculates the error locator polynomial for received word number 1. As shown, for large n and k values, the time to calculate the syndrome is significantly longer than the time to calculate the error locator polynomial. As such, the error locator polynomial module is idle for a substantial portion of time. At time T, the syndrome module calculates the syndrome for a third received word, the error locator polynomial module calculates the error locator polynomial for the second received word, and the Chien search module determines the error location for received word number one. As shown, the Chien search module may perform it function faster than the time it takes to calculate a syndrome. As such, the Chien search module may have idle time. As is known, the Chien search module may not have any idle time if the received code word is uncorrectable, i.e., has more errors than the value of t.
Therefore, a need exists for a method and apparatus of decoding BCH encoded signals for high data rates that minimizes circuitry, minimizes idle time, while maximizing circuitry utilization.